import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.io.{BufferedSource, Source}
import scala.util.Random

object MyKmeans {
  val k = 3
  val dim = 4
  val shold = 0.000001

  def main(args: Array[String]): Unit = {
    println("朱秉柯：183080106")
    var bs: BufferedSource = Source.fromFile("作业/resources/irisbezdek.data")
    val points: Array[Vector[Double]] = bs.getLines().map(line => {
      val parts: Array[Double] = line.substring(0, line.lastIndexOf(",")).split(",").map(_.toDouble)
      var vector: Vector[Double] = Vector[Double]()
      for (i <- 0 until dim)
        vector ++= Vector(parts(i))
      vector
    }).toArray
    bs = Source.fromFile("作业/resources/irisbezdek.data")
    val labels: Array[String] = bs.getLines().map(line => line.split("-")(1)).toArray
    val centers: Array[Vector[Double]] = initialCenters(k, points)
    kmeans(1000, points, centers, shold)
    printResult(points, centers, labels)
  }

  def initialCenters(k: Int, points: Array[Vector[Double]]): Array[Vector[Double]] = {
    var index = 0
    var temp = 0
    var array = new mutable.ListBuffer[Int]() //保存随机下标号
    while (index < k) {
      temp = new Random().nextInt(points.length)
      if (!array.contains(temp)) {
        array = array :+ temp
        index += 1
      }
    }
    val centers = new Array[Vector[Double]](k)
    println("初始化中心点：")
    for (i <- centers.indices) {
      centers(i) = points(array(i))
      println(centers(i))
    }
    centers
  }

  def kmeans(maxIterator: Int, points: Array[Vector[Double]], centers: Array[Vector[Double]], shold: Double): Unit = {
    var bool = true
    var newCenters: Array[Vector[Double]] = Array[Vector[Double]]()
    var move = 0.0
    var currentCost = 0.0
    var newCost = 0.0
    var count = 0
    var thold: Double = shold
    //clusterMap[Vector[Double],Array[Vector[Double]]] key:聚类中心，value:依赖于该聚类中心的点集
    while (bool) {
      count += 1
      move = 0.0
      currentCost = computeCost(points, centers)
      val cluster: Map[Vector[Double], Array[Vector[Double]]] = points.groupBy(v => closestCenter(centers, v))
      newCenters =
        centers.map((oldCenter: Vector[Double]) => {
          cluster.get(oldCenter) match {
            case Some(pointsInThisCluster) => //pointsInThisCluster:Array[Vector[Double]]
              //均值作为新的聚类中心
              vectorDivide(pointsInThisCluster.reduceLeft((v1, v2) => vectorAdd(v1, v2)), pointsInThisCluster.length)
            case None => oldCenter
          }
        })
      for (i <- centers.indices) {
        //move += math.sqrt(vectorDis(newCenters(i),centers(i)))
        centers(i) = newCenters(i)
      }
      newCost = computeCost(points, centers)
      println("currentCost：\t" + currentCost)
      println("newCost：\t\t" + newCost)
      thold = math.sqrt(vectorDis(Vector(currentCost), Vector(newCost)))
      if (thold < shold) {
        println("找到thold：" + thold)
        bool = false
      }
      //while-end
      if (count > maxIterator) {
        println("达到最大迭代次数退出，thold：" + thold.toString)
        bool = false
      }
    }
    println("寻找到的最优中心点：")
    for (i <- centers.indices) {
      println(centers(i))
    }

  }

  def printResult(points: Array[Vector[Double]], centers: Array[Vector[Double]], labels: Array[String]): Unit = {
    //将每个点的聚类中心用centers中的下标表示，属于同一类的点拥有相同的下标
    val pointsNum: Int = points.length
    val pointsLabel = new Array[Int](pointsNum)
    var closetCenter: Vector[Double] = Vector[Double]()
    val cluster: Map[Vector[Double], Array[Vector[Double]]] = points.groupBy(v => closestCenter(centers, v))
    println("聚类结果：")
    var rightCount = 0
    var prelabels = new ArrayBuffer[Int]()
    /*      for (i <- 0 until pointsNum) {
        closetCenter = centers.reduceLeft((c1, c2) => if (vectorDis(c1, points(i)) < vectorDis(c2, points(i))) c1 else c2)
        /*closetCenter.map(i=>{
          var str = ""
          if (i==0)
            str = "setosa"
          else if (i==1)
            str = "versicolor"
          else if (i==2)
            str = "virginica"
          str
        })*/
        /*val centerLabel: Array[String] =closetCenter.map(i=>{
          var str = ""
          var ii = i.toInt
          if (ii==0)
            str = "setosa"
          else if (ii==1)
            str = "versicolor"
          else if (ii==2)
            str = "virginica"
          else
            str = "default"
          str
        }).toArray*/
        pointsLabel(i) = centers.indexOf(closetCenter)
//        println(i+"--"+points(i) + "-----------" + pointsLabel(i))
        var str = ""
        if (pointsLabel(i)==0)
          str = "setosa"
        else if (pointsLabel(i)==1)
          str = "versicolor"
        else if (pointsLabel(i)==2)
          str = "virginica"
        else
          str = "default"
        if (str == labels(i))
          rightCount +=1
        prelabels.append(pointsLabel(i))
        println(i+"--"+points(i) + "-----------" + pointsLabel(i) + "--" + str+"--"+labels(i))
      }*/
    prelabels.take(50)
    while (rightCount.toDouble / labels.length < 0.8)
      rightCount = 0
    for (i <- 0 until pointsNum) {
      closetCenter = centers.reduceLeft((c1, c2) => if (vectorDis(c1, points(i)) < vectorDis(c2, points(i))) c1 else c2)
      /*closetCenter.map(i=>{
            var str = ""
            if (i==0)
              str = "setosa"
            else if (i==1)
              str = "versicolor"
            else if (i==2)
              str = "virginica"
            str
          })*/
      /*val centerLabel: Array[String] =closetCenter.map(i=>{
            var str = ""
            var ii = i.toInt
            if (ii==0)
              str = "setosa"
            else if (ii==1)
              str = "versicolor"
            else if (ii==2)
              str = "virginica"
            else
              str = "default"
            str
          }).toArray*/
      pointsLabel(i) = centers.indexOf(closetCenter)
      //        println(i+"--"+points(i) + "-----------" + pointsLabel(i))
      var str = ""
      if (pointsLabel(i) == 0)
        str = "setosa"
      else if (pointsLabel(i) == 1)
        str = "versicolor"
      else if (pointsLabel(i) == 2)
        str = "virginica"
      else
        str = "default"
      if (str == labels(i))
        rightCount += 1

    }
    /*for (i <- 0 until pointsNum) {
      prelabels.append(pointsLabel(i))
      println(i+"--"+points(i) + "-----------" + pointsLabel(i) + "--" + str+"--"+labels(i))
      }*/
    println("accuracy:" + rightCount.toDouble / labels.length)

  }

  // 找样本点所属聚类中心点
  def closestCenter(centers: Array[Vector[Double]], v: Vector[Double]): Vector[Double] = {
    //      centers.reduceLeft((c1, c2) =>
    //        if (vectorDis(c1, v) < vectorDis(c2, v)) c1 else c2
    //      )
    var tmp: Vector[Double] = centers(0)
    for (elem <- centers) {
      if (vectorDis(elem, v) < vectorDis(tmp, v))
        tmp = elem
    }
    tmp
  }


  def computeCost(points: Array[Vector[Double]], centers: Array[Vector[Double]]): Double = {
    val cluster: Map[Vector[Double], Array[Vector[Double]]] = points.groupBy(v => closestCenter(centers, v))
    var costSum = 0.0
    for (i <- centers.indices) {
      cluster.get(centers(i)) match {
        case Some(subSets) => //subSets:Array[Vector[Double]]()
          for (j <- subSets.indices) {
            costSum += vectorDis(centers(i), subSets(j)) * vectorDis(centers(i), subSets(j))
          }
        case None => costSum = costSum
      }
    }
    costSum
  }


  //向量间的欧式距离
  def vectorDis(v1: Vector[Double], v2: Vector[Double]): Double = {
    var distance = 0.0
    for (i <- v1.indices) {
      distance += (v1(i) - v2(i)) * (v1(i) - v2(i))
    }
    distance = math.sqrt(distance)
    distance
  }

  def vectorAdd(v1: Vector[Double], v2: Vector[Double]): Vector[Double] = {
    var added: Vector[Double] = v1
    for (i <- v1.indices)
      added = added.updated(i, v1(i) + v2(i))
    added
  }

  def vectorDivide(v: Vector[Double], num: Int): Vector[Double] = {
    var divided: Vector[Double] = v
    for (i <- v.indices)
      divided = divided.updated(i, divided(i) / num)
    divided
  }

}
